The present invention generally relates to management of computer networks, and relates more specifically to determining a path through a managed network.
A computer network generally includes a number of devices, including switches, routers and hubs, connected so as to allow communication among the devices. The devices within a network are often categorized into two classes: end stations such as workstations, desktop PCs, printers, servers, hosts, fax machines, and devices that primarily supply or consume information; and intermediate network devices such as gateways, switches and routers that primarily forward information between the other devices. A network management station may be used to monitor and manage the network. Typically, the network management station is a workstation that runs a network management software program. An example of a network management software program is CiscoWorks 2000, commercially available from Cisco Systems, Inc.
Sometimes, the configuration of the network or an error in the network can prevent information from being forwarded correctly. For example, an end-station such as a desktop PC may send data to a specified printer in the computer network but the data does not reach the specified printer due to the configuration of the network or an error in the network or because the printer does not support the same network protocol as that of the desktop PC. In order to determine the problem in the network, tools and techniques are needed to gather information about errors and configuration. One technique of gathering information about computer networks that use Internet Protocol is path tracing (xe2x80x9cIP path tracingxe2x80x9d). IP path tracing involves tracing the path that a packet would take starting at a source end-station, such as the desktop PC, to reach its destination such as the printer.
An example of a tool for IP path tracing is the xe2x80x9ctraceroutexe2x80x9d software program that is supported by UNIX-based network computers. Windows-based network computers support a similar software program called xe2x80x9ctracertxe2x80x9d. Both traceroute and tracert record the path or route comprising specific gateway computers or routers at each xe2x80x9chopxe2x80x9d through the computer network between a source computer and the destination computer. In a packet-switching network, a hop is the next intermediate gateway that a packet visits on its way to its destination. The traceroute program works by sending a small packet of data using Internet Control Message Protocol to the destination end-station. The packet includes a time limit value known as xe2x80x9ctime to livexe2x80x9d that is designed to be exceeded by the first gateway that receives the packet. In turn, the gateway returns a Time Exceeded message. The traceroute program increases the time limit value and resends the packet so that it will reach the next gateway in the path to the packet""s destination.
However, while many routers and network management stations support either the source-routed traceroute or source-routed tracert program, most end-stations do not. Examples of devices that neither support source-routed tracert nor source-routed traceroute are most end-stations and IP telephony equipment. IP telephony devices are devices that use Internet Protocol packet-switched connections to exchange voice, fax, and other information that have traditionally been carried over dedicated circuit-switched connections of the public switched telephone network. For those end-stations that do not support source-routed traceroute or source-routed tracert programs and are located remotely from the network management stations, IP path tracing is done by performing a direct tracert from the end-station to the packet""s destination. Performing a direct tracert from the end-station is usually inconvenient for a network manager who is remotely located from the end-station.
To illustrate, consider the following scenario. Susan, in the accounting department of ACME Company, would like to print a document on printer (xe2x80x9cDxe2x80x9d) from her desktop personal computer (xe2x80x9cSxe2x80x9d) but is unable to do so because S and D are not connected to the same network or are configured improperly. The computer network management department of ACME uses a Network Management Station (xe2x80x9cNxe2x80x9d) in an attempt to find the error. Assume that N is at a location remote from S and D. Further assume that S does not support the tracert program. In order for N to find the error in connectivity between S and D, N needs to perform IP path tracing between S and D using a source-routed tracert even if S does not support the source-routed tracert.
Based on the foregoing, there is a clear need for a mechanism allowing management of computer networks to determine a network path from a first device to a second device without relying on existing path tracing approaches.
In particular, there is a need for a method and mechanism that provides IP path tracing in a managed network using either source-routed traceroute or source-routed tracert program even though the source devices in the managed network neither support the source-routed traceroute nor the source-routed tracert program.
The foregoing needs, and other needs and objects that will become apparent for the following description, are achieved in the present invention, which comprises, in one aspect, a method for determining a path of a data packet in a managed network. In an embodiment, the method involves determining that a first subnet associated with a source node and a second subnet associated with a destination node are different subnets; determining a first gateway used by the source node to reach a network management node; determining a second gateway based on the first gateway and the destination node; determining whether the first subnet associated with the source node and a third subnet associated with the second gateway are identical subnets; and using the second gateway as a first hop from the source node to the destination node when the first subnet associated with the source node and the third subnet associated with the second gateway are identical.
One feature of this aspect is determining that the destination node is one hop away when the first subnet associated with the source node and the second subnet associated with the destination node are identical. According to another feature, the first gateway is used as the first hop from the source node to the destination node when the first subnet associated with the source node and the third subnet associated with the second gateway are not identical subnets.
In another feature, determining that the first subnet and second subnet are different subnets further involves determining a subnet mask associated with the source node; performing a Bitwise AND operation on the subnet mask and a first IP address associated with the source node to produce a first result; performing the Bitwise AND operation on the subnet mask and a second IP address associated with the destination node to produce a second result; and determining that the first subnet and the second subnet are different subnets when the first result is different from the second result.
In another feature, determining a subnet mask associated with the source node further involves determining a router that has an interface on the first subnet; and determining the subnet mask associated with the source node from a routing table of the router that has the interface on the first subnet. According to still another feature, determining a router further involves performing an IP path tracing operation from the network management node to the source node.
In another feature, the method further involves performing a PING operation with a record route option from the network management node to the source node. Also, performing an IP path tracing operation from the network management node to the source node further involves using a source-routed traceroute computer program to trace the IP path from the network management node to the source node. In another feature, determining the subnet mask further involves determining if there is a host route for the first IP address associated with the source node, and in response thereto, using the host route as an index for determining the subnet mask associated with the source node.
In another feature, determining the subnet mask associated with the source node further involves performing the Bitwise AND operation on a first mask and the first IP address associated with the source node to produce a first iteration result; and using the first iteration result as an index for determining the subnet mask associated with the source node when the first iteration result matches any entry in a route destination field of the routing table. According to another feature, the method further involves continuing to perform the Bitwise AND operation on a (1+N) mask and the first IP address associated with the source node to produce a (1+N) iteration result when the first iteration result does not match any entry in the route destination field of the routing table. The Bitwise AND operation on the (1+N) mask and the first IP address associated with the source node are discontinued the (1+N) iteration result is used as the index for determining the subnet mask associated with the source node when the (1+N) iteration result matches any entry in the route destination field of the routing table.
According to another aspect, a method for determining a path of a data packet in a managed network comprises the steps of determining that a first subnet associated with a source node and a second subnet associated with a destination node are different subnets; determining a set of all the routers that have an interface to the first subnet; determining for each router of the set of all routers that have an interface to the first subnet a next hop from the router to the destination node; determining whether the first subnet and a third subnet associated with the next hop from the router to the destination node are identical subnets; discounting the router as a first hop from the source node to the destination node when the first subnet and the third subnet are identical; and using the router as the first hop from the source node to the destination node when the first subnet and the third subnet are not identical.
In other aspects, the invention encompasses a computer apparatus, a computerreadable medium, and a carrier wave configured to carry out the foregoing steps.
Many other aspects and features will become apparent from the following description.